package pl.enigmatic.math.perm;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Vector;

import org.apache.log4j.xml.DOMConfigurator;

import pl.enigmatic.exception.WrongArgumentsException;
import pl.enigmatic.math.MathUtil;
import pl.enigmatic.util.Arrays;
import pl.enigmatic.util.Strings;


/**
 * <code>class</code> representing mathematical permutation. All operation are <code>0</code>-based, so a permutation on <code>n</code> elements will
 * act on elements from <code>0</code> to <code>n - 1</code>. All operations on index values wrap the passed index to make it safe to use any value as
 * an index. If for instance we call <code>at(-1)</code> on a permutation we will be given the value of last but one index, i.e.
 * <code>at(n - 2)</code>.
 * @author reggie_7
 */
@SuppressWarnings("serial")
public class Permutation implements Serializable, Cloneable, Iterable<Permutation.Point> {

	public class Point {

		private final int index;

		protected Point(final int index) {
			this.index = index;
		}

		public int getIndex() {
			return index;
		}

		public Point getNext() {
			return points[at(index)];
		}

		public Point getPrev() {
			return points[invAt(index)];
		}

		public boolean isFixed() {
			return isFixedAt(index);
		}

		public void removeCycle() {
			Permutation.this.removeCycle(index);
		}

		public Point power(final int m) {
			return points[powerAt(m, index)];
		}

		public int[] getCycle() {
			return Permutation.this.getCycle(index);
		}

		public String getSymbol() {
			return Permutation.this.getSymbol(index).toString();
		}

		public String toString() {
			return getSymbol();
		}
	}

	public class Cycle implements Iterable<Point>, Comparable<Cycle> {

		protected final int[] array;

		public Cycle(final int[] array) {
			this.array = array;
		}

		public int length() {
			return array.length;
		}

		public int at(final int index) {
			return array[index];
		}

		public Point get(final int index) {
			return points[at(index)];
		}

		@Override
		public Iterator<Point> iterator() {
			return new Iterator<Point>() {

				private int next = 0;

				@Override
				public boolean hasNext() {
					return next < length();
				}

				@Override
				public Point next() {
					return get(next++);
				}

				@Override
				public void remove() {
					throw new UnsupportedOperationException();
				}
			};
		};

		@Override
		public String toString() {
			final StringBuilder s = new StringBuilder();
			s.append("(");
			for (final Point p : this) {
				s.append(p);
			}
			s.append(")");
			return s.toString();
		}

		@Override
		public int compareTo(final Cycle c) {
			if (length() != c.length()) { return length() - c.length(); }
			final int min[] = new int[] { Integer.MAX_VALUE, Integer.MAX_VALUE };
			for (final int i : array) {
				min[0] = Math.min(i, min[0]);
			}
			for (final int i : c.array) {
				min[1] = Math.min(i, min[1]);
			}
			return min[0] - min[1];
		}
	}

	public static class CyclesList extends ArrayList<Cycle> {

		public String toString() {
			StringBuilder s = new StringBuilder();
			for (Cycle c : this) {
				s.append(c);
			}
			return s.toString();
		}
	}

	static {
		DOMConfigurator.configure("log4j.xml");
	}

	/** logging utility object */
	private static final org.apache.log4j.Logger logger = org.apache.log4j.Logger.getLogger(Permutation.class);

	private static int[] makeCorrect(final Map<Integer, Integer> map, int[] res, final int max) {
		final Collection<Integer> val = map.values();
		res = Arrays.fill(res, 0, max, -1);
		for (final Entry<Integer, Integer> e : map.entrySet()) {
			res[e.getKey()] = e.getValue();
		}
		final List<Integer> list = new ArrayList<Integer>();
		for (final int i : Arrays.identity(max + 1)) {
			if (!val.contains(i)) {
				list.add(i);
			}
		}
		for (int i = 0; i < res.length; i++) {
			if (res[i] < 0) {
				int x = 0;
				if (list.contains(i)) {
					x = list.indexOf(i);
				}
				res[i] = list.get(x);
				list.remove(x);
			}
		}
		return res;
	}

	public static int[] makeCorrect(final Map<Integer, Integer> map, final int[] res) {
		return makeCorrect(map, res, MathUtil.max(MathUtil.max(map.values()), MathUtil.max(map.keySet())));
	}

	public static int[] makeCorrect(final Map<Integer, Integer> map) {
		final int max = MathUtil.max(MathUtil.max(map.values()), MathUtil.max(map.keySet()));
		return makeCorrect(map, new int[max + 1], max);
	}

	/**
	 * Checks whether the given <code>array</code> can be used to define a permutation.
	 * @param array the array to check
	 * @return <code>true</code>, if <code>array</code> can define a permutation
	 */
	protected static boolean isCorrect(final int[] array) {
		final boolean[] taken = Arrays.constant(array.length, false);
		for (int i = 0; i < array.length; i++) {
			if (array[i] < 0 || array[i] > array.length || taken[array[i]]) { return false; }
			taken[array[i]] = true;
		}
		return true;
	}

	/** an array with permutation elements */
	private final int[] array;
	private final Point[] points;

	/**
	 * Creates a permutation represented by the given array.
	 * @param array the permutation array representation
	 */
	public Permutation(int[] array) {
		this.array = new int[array.length];
		points = new Point[array.length];
		array = wrapSafe(array);
		for (int i = 0; i < array.length; i++) {
			this.array[i] = array[i];
			points[i] = new Point(i);
		}
		if (this.array == null) {
			logger.error(String.format("Permutation array cannot be null."), new WrongArgumentsException());
		} else if (!isCorrect(this.array)) {
			logger.error(String.format("Wrong permutation array."), new WrongArgumentsException());
		}
	}

	/**
	 * Creates an identity permutation with the given <code>length</code>. If <code>length</code> is less than 0, then the permutation will be empty -
	 * having length 0.
	 * @param length the length of the created permutation
	 * */
	public Permutation(final int length) {
		this(Arrays.identity(MathUtil.clampBottom(0, length)));
	}

	/**
	 * @param position the position to be wrapped
	 * @return a position value wrapped to the range from <code>0</code> to <code>length() - 1</code>
	 */
	private int wrapSafe(final int position) {
		return MathUtil.wrap(0, array.length - 1, position);
	}

	/**
	 * @param positions the positions array to be wrapped
	 * @return a new <code>positions</code> array with values wrapped to the range from <code>0</code> to <code>length() - 1</code>
	 */
	private int[] wrapSafe(final int[] positions) {
		final int[] array = new int[positions.length];
		for (int i = 0; i < positions.length; i++) {
			array[i] = wrapSafe(positions[i]);
		}
		return array;
	}

	/**
	 * @param set the positions set to be wrapped
	 * @return a new set of <code>positions</code> with values wrapped to the range from <code>0</code> to <code>length() - 1</code>
	 */
	private HashSet<Integer> wrapSafe(final HashSet<Integer> set) {
		final HashSet<Integer> res = new HashSet<Integer>();
		for (final Integer x : set) {
			res.add(wrapSafe(x));
		}
		return res;
	}

	/**
	 * @return the <code>length</code> of this permutation
	 * */
	public int length() {
		return array.length;
	}

	/**
	 * @return an array with the elements of <code>this</code> permutation
	 * */
	public int[] array() {
		final int[] res = new int[length()];
		for (int i = 0; i < length(); i++) {
			res[i] = array[i];
		}
		return res;
	}

	/**
	 * Retrieves the value of <code>this</code> permutation at the given <code>position</code>.
	 * @param position the position to investigate
	 * @return the value of <code>this</code> permutation at the specified <code>position</code>
	 */
	public int at(final int position) {
		return array[wrapSafe(position)];
	}

	public Object getSymbol(final int position) {
		return position;
	}

	/**
	 * Retrieves the value of the multiplical inverse of <code>this</code> permutation at the given <code>position</code>.
	 * @param position the position to investigate
	 * @return the value of the inverse of <code>this</code> permutation at the specified <code>position</code>
	 */
	public int invAt(int position) {
		position = wrapSafe(position);
		for (int i = 0; i < length(); i++) {
			if (array[i] == position) { return i; }
		}
		return -1;
	}

	/**
	 * Checks whether <code>this</code> permutation fixes the value at the given <code>position</code>, i.e. whether we have
	 * <code>position == at(position)</code>
	 * @param position the position to investigate
	 * @return <code>true</code>, if <code>position == at(position)</code>
	 */
	public boolean isFixedAt(int position) {
		position = wrapSafe(position);
		return position == at(position);
	}

	/**
	 * @return all the fixed points in <code>this</code> permutation
	 */
	public Set<Integer> getFixedPoints() {
		final Set<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < array.length; i++) {
			if (isFixedAt(i)) {
				set.add(i);
			}
		}
		return set;
	}

	/**
	 * Sets all elements in the cycle containng <code>position</code> to identity.
	 * @param position a position identifying the cycle to be removed
	 * @return <code>true</code>, if any changes were made (there was nontrivial cycle)
	 */
	public boolean removeCycle(int position) {
		position = wrapSafe(position);
		int j = at(position);
		final boolean res = array[position] != position;
		array[position] = position;
		while (position != j) {
			final int l = array[j];
			array[j] = j;
			j = l;
		}
		return res;
	}

	/**
	 * Checks whether <code>this</code> permutation contains a cycle described by <code>c</code>: <br/>
	 * (<code>c[0]</code>, <code>c[1]</code>, ..., <code>c[c.length-1]</code>)
	 * @param c cycle to check
	 * @return <code>true</code>, if this contains cycle <code>c</code>
	 */
	public boolean containsCycle(int... c) {
		if (c == null || c.length == 0) { return true; }
		c = wrapSafe(c);
		int i = 1;
		while (i < c.length && at(c[i - 1]) == c[i]) {
			i++;
		}
		return i == c.length && at(c[c.length - 1]) == c[0];
	}

	/**
	 * Checks whether <code>this</code> contains a transposition on elements <code>i</code> and <code>j</code>.
	 * @param i element of transpotiotion
	 * @param j element of transpotiotion
	 * @return <code>true</code>, if this contains a transposition (<code>i</code>, <code>j</code>)
	 */
	public boolean transposes(final int i, final int j) {
		return containsCycle(i, j);
	}

	/**
	 * Checks whether <code>this</code> permutation is an identity.
	 * @return <code>true</code>, if <code>this</code> is an identity permutation
	 */
	public boolean isIdentity() {
		for (int i = 0; i < array.length; i++) {
			if (!isFixedAt(i)) { return false; }
		}
		return true;
	}

	/**
	 * Ckecks whether <code>this</code> contains a subpermutation on the given <code>set</code> of points.
	 * @param set the set of point to cut to
	 * @return <code>true</code>, if <code>this</code> cut to <code>set</code> is a permutation again
	 */
	public boolean canCutTo(HashSet<Integer> set) {
		set = wrapSafe(set);
		for (final Integer x : set) {
			if (!set.contains(at(x))) { return false; }
		}
		return true;
	}

	/**
	 * Ckecks whether <code>this</code> contains a subpermutation on the given <code>set</code> of points.
	 * @param set the set of point to cut to
	 * @return <code>true</code>, if <code>this</code> cut to <code>set</code> is a permutation again
	 */
	public boolean canCutTo(final int... set) {
		final HashSet<Integer> points = new HashSet<Integer>();
		for (final int point : set) {
			points.add(point);
		}
		return canCutTo(points);
	}

	/**
	 * Checks whether <code>this</code> is an involution.
	 * @return <code>true</code>, if <code>this</code> is an involution
	 */
	public boolean isInvolution() {
		if (length() % 2 == 1) { return false; }
		for (int i = 0; i < length(); i++) {
			if (at(at(i)) != i) { return false; }
		}
		return true;
	}

	/**
	 * Checks whether <code>this</code> has fixed points.
	 * @return <code>true</code>, if <code>this</code> contains any fixed points
	 */
	public boolean hasFixedPoints() {
		for (int i = 0; i < length(); i++) {
			if (isFixedAt(i)) { return true; }
		}
		return false;
	}

	/** Inverses <code>this</code> permutation in the sense of permutation algebra multiplication. */
	public void inverse() {
		final int[] tmp = array();
		for (int i = 0; i < length(); i++) {
			array[tmp[i]] = i;
		}
	}

	/**
	 * Reverses <code>this</code> in the following sense:<br/>
	 * <code>this[i]</code> &larr; <code>this[length - i]</code>
	 */
	public void reverse() {
		final int[] tmp = array();
		final int l = length();
		for (int i = 0; i < l; i++) {
			array[i] = tmp[l - i - 1];
		}
	}

	/**
	 * Reverses <code>this</code> in the following sense:<br/>
	 * <code>this[i]</code> &larr; <code>this[i+1]</code> and <code>this[i+1]</code> &larr; <code>this[i]</code>, where <code>i</code> =
	 * <code>0</code>, <code>2</code>, <code>4</code>, ....<br/>
	 * If the length is odd - the last element remains unchanged.
	 */
	public void neighbor() {
		final int[] tmp = array();
		for (int i = 0; i < length(); i += 2) {
			array[i] = tmp[i + 1];
			array[i + 1] = tmp[i];
		}
	}

	/**
	 * Shifts <code>this</code> to right with the given <code>shift</code> distance.
	 * @param shift the shift distance value
	 */
	public void shift(int shift) {
		shift = MathUtil.mod(-shift, length());
		final int[] array = array();
		for (int i = 0; i < length(); i++) {
			this.array[i] = array[(i + shift) % length()];
		}
	}

	/**
	 * Cycles <code>this</code> permutation in the way iven by the cycle <code>c</code>, i.e.:<br/>
	 * <code>this(c(0))</code> &larr; <code>this(c(1))</code><br/>
	 * <code>this(c(1))</code> &larr; <code>this(c(2))</code><br/>
	 * ...
	 * @param c the cycle to use
	 */
	public void cycle(int... c) {
		if (c != null && c.length > 0) {
			c = wrapSafe(c);
			final int tmp = array[c[0]];
			for (int i = 0; i < c.length - 1; i++) {
				array[c[i]] = array[c[i + 1]];
			}
			array[c.length - 1] = tmp;
		}
	}

	/**
	 * Transposes values at the given positions.
	 * @param i the first position
	 * @param j the second position
	 */
	public void transpose(final int i, final int j) {
		cycle(i, j);
	}

	/**
	 * Multiplies <code>this</code> permutation by the given <code>right</code> permutation. After this call <code>this</code> becomes
	 * <code>this * right</code>.
	 * @param right the permutation to multiply by
	 */
	public void multiply(final Permutation right) {
		if (right.length() != length()) { return; }
		final int[] tmp = array();
		for (int i = 0; i < length(); i++) {
			array[i] = tmp[right.array[i]];
		}
	}

	/**
	 * Multiplies <code>this</code> permutation by the given <code>left</code> permutation. After this call <code>this</code> becomes
	 * <code>left * this</code>.
	 * @param left the permutation to multiply by
	 */
	public void multiplyLeft(final Permutation left) {
		if (left.length() != length()) { return; }
		final int[] tmp = array();
		for (int i = 0; i < length(); i++) {
			array[i] = left.array[tmp[i]];
		}
	}

	/**
	 * Conjugates <code>this</code> by the given permutation. After this call <code>this</code> becomes <code>sigma * this * sigma^(-1)</code>.
	 * @param sigma the conjugating permutation
	 */
	public void conjugate(final Permutation sigma) {
		multiplyLeft(sigma);
		final Permutation inv = new Permutation(sigma.array());
		inv.inverse();
		multiply(inv);
	}

	/**
	 * Sets <code>this</code> to identity permutation.
	 */
	public void identity() {
		for (int i = 0; i < array.length; i++) {
			array[i] = i;
		}
	}

	/**
	 * Rotates <code>this</code> <code>rot</code> times. The rotation is the same as applying conjugation by a shift one permutation.
	 * @param rot the number of rotations to do
	 */
	public void rotate(int rot) {
		final int[] tmp = array();
		final int l = length();
		rot = MathUtil.mod(-rot, l);
		rot = (l - rot) % l;
		for (int i = 0; i < l; i++) {
			array[(i + rot) % l] = (tmp[i] + rot) % l;
		}
	}

	/**
	 * Sets <code>this</code> to its <code>m</code>-th power.
	 * @param m the power to use
	 */
	public void power(int m) {
		final Permutation temp = new Permutation(array());
		if (m < 0) {
			m *= -1;
			temp.inverse();
		}
		identity();
		while (m > 0) {
			if (m % 2 == 0) {
				m /= 2;
				temp.multiplyLeft(temp);
			} else {
				m -= 1;
				multiplyLeft(temp);
			}
		}
	}

	/**
	 * Finds the <code>m</code>-th power of this permutation at the given <code>position</code>.
	 * @param m the power to use
	 * @param position the position to find the power at
	 * @return <code>m</code>-th power of this permutation at the given <code>position</code>
	 */
	public int powerAt(int m, final int position) {
		int result = wrapSafe(position);
		m = MathUtil.mod(m, length());
		while (m > 0) {
			m -= 1;
			result = at(result);
		}
		return result;
	}

	/**
	 * Finds the cycle beginning at the given <code>x</code> point.
	 * @param x the starting point of the desired cycle
	 * @return the cycle starting at <code>x</code>
	 */
	public int[] getCycle(int x) {
		x = wrapSafe(x);
		final Vector<Integer> vec = new Vector<Integer>();
		int y = x;
		do {
			vec.add(y);
			y = at(y);
		} while (x != y);
		final int[] res = new int[vec.size()];
		for (int i = 0; i < res.length; i++) {
			res[i] = vec.get(i);
		}
		return res;
	}

	/**
	 * Finds all the non-trivial cycles in <code>this</code> permutation and returns this representation.
	 * @return the cycle representaton of <code>this</code> permutation
	 */
	public int[][] getAllCycles() {
		final Set<Integer> all = new HashSet<Integer>();
		for (int i = 0; i < array.length; i++) {
			all.add(i);
		}
		final Vector<int[]> vec = new Vector<int[]>();
		while (!all.isEmpty()) {
			final int[] cycle = getCycle((Integer) all.toArray()[0]);
			if (cycle.length > 1) {
				vec.add(cycle);
			}
			for (final int x : cycle) {
				all.remove(x);
			}
		}
		final int[][] res = new int[vec.size()][];
		int i = 0;
		for (final int[] cycle : vec) {
			res[i++] = cycle;
		}
		return res;
	}

	public CyclesList getCycles() {
		final CyclesList list = new CyclesList();
		for (final int[] c : getAllCycles()) {
			list.add(new Cycle(c));
		}
		return list;
	}

	/**
	 * Enciphers the given <code>plaintext</code> array by <code>this</code> permutation.
	 * @param plaintext the plaintext to use
	 * @return enciphered array: <code>(this(plaintext[0], this(plaintext[1], ...))</code>
	 */
	public int[] encipher(final int... plaintext) {
		final int[] res = new int[plaintext.length];
		for (int i = 0; i < plaintext.length; i++) {
			res[i] = at(plaintext[i]);
		}
		return res;
	}

	/**
	 * Makes <code>this</code> an involution.
	 * @return true, if <code>this</code> already was an involution
	 */
	public boolean involutionize() {
		if (!isInvolution()) {
			final int[][] cycles = getAllCycles();
			final int[] array = Arrays.identity(length());
			for (final int[] cycle : cycles) {
				for (int i = 1; i < cycle.length; i += 2) {
					array[cycle[i - 1]] = cycle[i];
					array[cycle[i]] = cycle[i - 1];
				}
			}
			set(array);
		}
		return false;
	}

	/**
	 * Makes <code>this</code> a no-fixed-points permutation.
	 * @return true, if <code>this</code> already had no fixed points
	 */
	public boolean removeFixedPoints() {
		if (length() > 1) {
			final Set<Integer> set = getFixedPoints();
			if (set.size() == 1) {
				final int fixed = (Integer) set.toArray()[0];
				final int[] cycle;
				if (fixed == 0) {
					cycle = getCycle(1);
				} else {
					cycle = getCycle(0);
				}
				array[cycle[cycle.length - 1]] = fixed;
				array[fixed] = cycle[0];
			} else if (!set.isEmpty()) {
				final Integer[] fixed = new Integer[set.size()];
				set.toArray(fixed);
				int i = 1;
				if (fixed.length % 2 != 0) {
					array[fixed[0]] = fixed[1];
					array[fixed[1]] = fixed[2];
					array[fixed[2]] = fixed[0];
					i = 4;
				}
				for (; i < fixed.length; i += 2) {
					array[fixed[i - 1]] = fixed[i];
					array[fixed[i]] = fixed[i - 1];
				}
			}
		}
		return false;
	}

	// TODO javadoc
	// zwraca kol||owanie inwolucji bez punktow stalych, kt||e daje optymalne
	// ulozenie bez przeciec kabli w schemacie walca odwracajacego
	public int[][] bestInvCol() { // zwraca tablicę 13x3 postaci: (1szy z pary
		// i, 2gi z pary i, poziom ułożenia i) po
		// i=0,...,12
		if (!isInvolution()) { return null; }

		final int[][] pairs = getAllCycles();
		final int[][] res = new int[pairs.length][3];
		final int[] dists = new int[pairs.length];
		final int[] level = new int[pairs.length];
		for (int i = 0; i < pairs.length; i++) {
			dists[i] = pairs[i][1] - pairs[i][0];
			res[i][0] = pairs[i][0];
			res[i][1] = pairs[i][1];
			level[i] = 1;
		}

		// 0 - pary identyczne lub rozlaczne
		// 1 - pary sie przecinaja
		// 2 - jedna para zawiera druga (para o mniejszym indeksie zawiera par o
		// indeksie wiekszym)
		final int[][] sections = new int[pairs.length][pairs.length];
		for (int i = 0; i < pairs.length; i++) {
			for (int j = 0; j < pairs.length; j++) {
				if (i >= j) {
					if (i == j) {
						sections[i][j] = 0;
					} else {
						sections[i][j] = sections[j][i];
					}
				} else if (pairs[i][1] < pairs[j][0]) {
					sections[i][j] = 0;
				} else if (pairs[i][1] > pairs[j][1]) {
					sections[i][j] = 2;
				} else {
					sections[i][j] = 1;
				}
			}
		}

		java.util.Arrays.sort(dists);
		int d = 0;
		while (d < dists.length - 1) {
			if (dists[d] == dists[d + 1]) {
				dists[d] = 0;
			}
			d++;
		}

		for (d = 0; d < dists.length; d++) {
			if (dists[d] != 0) {
				for (int i = 0; i < pairs.length; i++) {
					final int[] pi = pairs[i];
					if (pi[1] - pi[0] == dists[d]) {
						for (int j = 0; j < pairs.length; j++) {
							final int[] pj = pairs[j];
							if ((pj[1] - pj[0] < dists[d] || pj[1] - pj[0] == dists[d] && j < i) && level[i] <= level[j] && sections[i][j] > 0) {
								level[i] = level[j] + 1;
							}
						}
					}
				}
			}
		}

		for (int i = 0; i < pairs.length; i++) {
			res[i][2] = level[i];
		}

		return res;
	}

	/**
	 * Uses the <code>array</code> parameter as the new definition of <code>this</code> permutation.
	 * @param array the array to use as a permutation definition
	 * @return <code>true</code>, if the call was succesfull, <code>false</code> - if there were no changes made
	 */
	public boolean set(int[] array) {
		array = wrapSafe(array);
		if (array == null || array.length != this.array.length || !isCorrect(array)) {
			return false;
		} else {
			for (int i = 0; i < array.length; i++) {
				this.array[i] = array[i];
			}
			return true;
		}
	}

	/**
	 * Sets <code>this</code> permutation from the given <code>cycles</code>.
	 * @param cycles two dimensional array representing cycles
	 * @return <code>true</code>, if the call was succesfull, <code>false</code> - if there were no changes made
	 */
	public boolean set(final int[][] cycles) {
		if (cycles == null) {
			return false;
		} else {
			final int[] array = Arrays.identity(length());
			final boolean[] taken = Arrays.constant(length(), false);
			for (int[] cycle : cycles) {
				cycle = wrapSafe(cycle);
				for (int j = 0; j < cycle.length; j++) {
					if (taken[cycle[j]]) {
						return false;
					} else {
						array[cycle[j]] = cycle[(j + 1) % cycle.length];
						taken[cycle[j]] = true;
					}
				}
			}
			for (int i = 0; i < array.length; i++) {
				this.array[i] = array[i];
			}
			return true;
		}
	}

	/**
	 * Uses the <code>array</code> of the parameter permutation as the new definition of <code>this</code> permutation.
	 * @param other the permutation to copy from
	 * @return <code>true</code>, if the call was succesfull, <code>false</code> - if there were no changes made
	 */
	public boolean copy(final Permutation other) {
		return set(other.array);
	}

	/**
	 * Tries to clone <code>this</code> object instance.
	 * @see java.lang.Object#clone()
	 */
	@Override
	public Permutation clone() {
		return new Permutation(array);
	}

	/**
	 * @return horizontal string representation of <code>this</code> permutation.
	 */
	public String toStringH() {
		return Strings.toString(array);
	}

	/**
	 * Converts <code>this</code> permutation to a string representation. Each mapping is given in a new line. Each line is started with the given
	 * <code>prefix</code>.
	 * @param prefix prefix starting each line
	 * @return vertical string representation of <code>this</code> permutation.
	 */
	public String toStringV(final String prefix) {
		String result = "";
		for (int i = 0; i < length() - 1; i++) {
			result += prefix + Integer.toString(i) + "->" + Integer.toString(at(i)) + '\n';
		}
		result += prefix + Integer.toString(length() - 1) + "->" + Integer.toString(at(length() - 1));
		return result;
	}

	/**
	 * Converts <code>this</code> permutation to a string representation. Each mapping is given in a new line.
	 * @return vertical string representation of <code>this</code> permutation.
	 */
	public String toStringV() {
		return toStringV("");
	}

	/**
	 * Converts <code>this</code> permutation to a cycle decomposition string representation.
	 * @return cycle decomposition string representation of <code>this</code> permutation.
	 */
	public String toStringC() {
		String result = "";
		final int cycles[][] = getAllCycles();
		if (cycles.length == 0) { return "()"; }
		for (final int[] cycle : cycles) {
			result += Strings.toString(cycle, ",", "(", ")");
		}
		return result;
	}

	/**
	 * @see Permutation#toStringH()
	 */
	@Override
	public String toString() {
		return getClass().getSimpleName() + ": " + toStringH();
	}

	@Override
	public Iterator<Point> iterator() {
		return new Iterator<Permutation.Point>() {

			private int current = 0;

			@Override
			public boolean hasNext() {
				return current < length();
			}

			@Override
			public Point next() {
				return points[current++];
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException("Removing points from permutation is not allowed.");
			}
		};
	}
}